/**
 * 给出一棵二叉树，其上每个结点的值都是0或1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
 *
 * 例如，如果路径为0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数01101，也就是13。
 * 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
 *
 * 返回这些数字之和。题目数据保证答案是一个 32 位 整数。
 * https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
 * 思路：迭代
 */
class SumRootToLeafDieDai {
    public int sumRootToLeaf(TreeNode root) {
        int ans=0,sum=0;//答案、当前栈顶节点表示的值
        Stack<TreeNode> stack=new Stack<>();
        TreeNode pre=null;//记录上一刚刚轮遍历过的节点，只记录含“右节点”的部分
        while(root!=null||!stack.isEmpty()){
            //对于while里面条件解释：1、栈内没有节点了，那么无需继续；2、root==null，说明最后遍历过的那一支已经遍历完成了
            //ook：首先，规则是，对于一个节点，需要先遍历左支，再遍历右支
            while(root!=null){
                sum=sum*2+root.val;
                stack.push(root);
                root=root.left;
            }
            //这一支的无限左支已经到尽头（本循环最开始root的左支节点全部入栈），需要进行操作来统计数据：
            root=stack.peek();//此时这个节点对应的是sum，不要着急pop呀，就这里出岔子好久
            //root要么是叶节点，要么它的右支有可能没有遍历过（因为上边的规则是先遍历左支呀）
            if(root.left==null&&root.right==null){
                //root是叶节点，此时需要加上，并且sum需要去掉一位
                ans+=sum;
                sum/=2;
                pre=stack.pop();
                root=null;//为了标记这一支以及下面已经遍历完成表示左右都不用向下了
            }
            else if(root.right==null||root.right==pre){
                //此时右节点为空或者右节点已经被遍历过，则需要返回上一层：
                pre=stack.pop();
                sum/=2;
                root=null;//为了标记这一支以及下面已经遍历完成表示左右都不用向下了
            }
            else{
                //此时右支没有遍历，那么就先把此时的第一个右节点拿进来
                root=root.right;                               
                //这样就遍历到某个“右支”的起始位置了，下次循环需要重复上述ook操作
            }
        }
        return ans;
    }
}
